#!/usr/bin/env python
# -*- coding: utf-8 -*-
# @Time    : 2025/3/20
# @USER    : Shengji He
# @File    : FindCountGoodIntegers.py
# @Software: PyCharm
# @Version  : Python-
# @TASK:
from typing import List
from math import factorial
from collections import Counter

from utils import timer_decorator

"""
- Hash Table
- Math
- Combinatorics
- Enumeration
"""


class Solution:
    """
    [3272. Find the Count of Good Integers](https://leetcode.com/problems/find-the-count-of-good-integers/description/)

    You are given two positive integers n and k.

    An integer x is called k-palindromic if:

    x is a palindrome.
    x is divisible by k.
    An integer is called good if its digits can be rearranged to form a k-palindromic integer. For example, for k = 2, 2020 can be rearranged to form the k-palindromic integer 2002, whereas 1010 cannot be rearranged to form a k-palindromic integer.

    Return the count of good integers containing n digits.

    Note that any integer must not have leading zeros, neither before nor after rearrangement. For example, 1010 cannot be rearranged to form 101.

    Example 1:
        Input: n = 3, k = 5
        Output: 27

        Explanation:

        Some of the good integers are:
            - 551 because it can be rearranged to form 515.
            - 525 because it is already k-palindromic.

    Example 2:
        Input: n = 1, k = 4
        Output: 2

        Explanation:
        The two good integers are 4 and 8.

    Example 3:
        Input: n = 5, k = 6
        Output: 2468

    Constraints:
        - 1 <= n <= 10
        - 1 <= k <= 9

    """

    @staticmethod
    def get_combination(x: List[str], flag: bool = False):
        num = len(x)
        if num == 1:
            return x
        out = []
        for i in range(num):
            if flag and x[i] == '0':
                continue
            if x[i] in x[:i]:
                continue
            for j in Solution.get_combination(x[:i] + x[i + 1:]):
                out.append(x[i] + j)
        return out

    def countGoodIntegers(self, n: int, k: int) -> int:
        # ! too slow
        # low = 10 ** (n - 1)
        # high = 10 ** n
        # candidate_pn = []
        # for number in range(low, high):
        #     number_str = str(number)
        #     if number_str == number_str[::-1] and number % k == 0:
        #         candidate_pn.append(number_str)

        half = (n + 1) // 2
        low = 10 ** (half - 1)
        high = 10 ** half
        start = n % 2
        candidate_pn = []
        for number in range(low, high):
            number_str = str(number)
            number_str += number_str[::-1][start:]
            if int(number_str) % k == 0:
                candidate_pn.append(number_str)

        count = 0
        exist_values = []

        subset_num = {}

        for pn_str in candidate_pn:
            # if pn_str in exist_values:
            #     continue
            temp = sorted([i for i in pn_str])
            if temp in exist_values:
                continue
            exist_values.append(temp)

            # hash
            hash_value = str(pn_str.count('0'))
            cur_hash_list = []
            for i in range(1, 10):
                num = pn_str.count(str(i))
                if num != 0:
                    cur_hash_list.append(str(num))
            hash_value += ''.join(sorted(cur_hash_list))

            if hash_value in subset_num.keys():
                cur_sum = subset_num[hash_value]
            else:
                cur_out = Solution.get_combination(temp, True)

                cur_sum = len(cur_out)

                subset_num[hash_value] = cur_sum

            count += cur_sum
        return count

    @timer_decorator
    def countGoodIntegers_ai(self, n: int, k: int) -> int:
        m = (n + 1) // 2
        start = 10 ** (m - 1)
        end = 10 ** m
        k_palindromes = []

        for prefix in range(start, end):
            s = str(prefix)
            if n % 2 == 1:
                pal = s + s[:-1][::-1]
            else:
                pal = s + s[::-1]
            pal_num = int(pal)
            if pal_num % k == 0:
                k_palindromes.append(pal)

        # 收集所有唯一的频次模式
        freq_patterns = set()
        for digits in k_palindromes:
            cnt = Counter(digits)
            # 转换为按字符排序的元组列表
            items = sorted(cnt.items())
            freq_patterns.add(tuple(items))

        total = 0
        for pattern in freq_patterns:
            freq = {int(d): count for d, count in pattern}
            # 计算总排列数，组合数学中的多重集合排列公式
            current_total = factorial(n)
            for cnt in freq.values():
                current_total //= factorial(cnt)
            # 计算前导零的排列数
            if 0 in freq:
                invalid = factorial(n - 1)
                new_freq = freq.copy()
                new_freq[0] -= 1
                if new_freq[0] == 0:
                    del new_freq[0]
                for cnt in new_freq.values():
                    invalid //= factorial(cnt)
                current_total -= invalid
            total += current_total

        return total

    @timer_decorator
    def countGoodIntegers_v2(self, n: int, k: int) -> int:
        half = (n + 1) // 2
        low = 10 ** (half - 1)
        high = 10 ** half
        start = n % 2
        k_palindromes = []
        for number in range(low, high):
            number_str = str(number)
            number_str += number_str[::-1][start:]
            if int(number_str) % k == 0:
                k_palindromes.append(number_str)

        count = 0
        freq_patterns = set()
        for digits in k_palindromes:
            cnt = Counter(digits)
            items = sorted(cnt.items())
            freq_patterns.add(tuple(items))

        total = 0
        same_freq = {}
        for pattern in freq_patterns:
            freq = {int(d): count for d, count in pattern}
            hash_value = ''.join(map(str, [i[1] for i in pattern]))
            if pattern[0][0] != '0':
                hash_value = '0' + hash_value
            if hash_value in same_freq:
                current_total = same_freq[hash_value]
            else:
                # 计算总排列数，组合数学中的多重集合排列公式
                current_total = factorial(n)
                for cnt in freq.values():
                    current_total //= factorial(cnt)
                # 计算前导零的排列数
                if 0 in freq:
                    invalid = factorial(n - 1)
                    new_freq = freq.copy()
                    new_freq[0] -= 1
                    if new_freq[0] == 0:
                        del new_freq[0]
                    for cnt in new_freq.values():
                        invalid //= factorial(cnt)
                    current_total -= invalid

                same_freq[hash_value] = current_total

            total += current_total

        return total


if __name__ == '__main__':
    # n = 3
    # k = 5

    n = 9
    k = 4

    # n = 5
    # k = 6

    S = Solution()

    # print(S.countGoodIntegers(n, k))
    print(S.countGoodIntegers_ai(n, k))
    print(S.countGoodIntegers_v2(n, k))
    print('done')
